# import sortedcontainers
# class Solution(object):
#     def subarraysWithMoreZerosThanOnes(self, nums):
#         d = sortedcontainers.SortedList()
#         now = 0
#         d.add(0)
#         ans = 0
#         base = 10 ** 9 + 7
#         for num in nums:
#             if num == 1:
#                 now += 1
#             else:
#                 now -= 1
#             ans += d.bisect_left(now)
#             d.add(now)
#         return ans % base

# O(n)
import collections
class Solution(object):
    def subarraysWithMoreZerosThanOnes(self, nums):
        ants = collections.defaultdict(int)
        ants[0] = 1
        cnt = 0
        now = 0
        ans = 0
        base = 10 ** 9 + 7
        for num in nums:
            if num:
                cnt += ants[now]
                now += 1
            else:
                now -= 1
                cnt -= ants[now]
            ans += cnt
            ants[now] += 1
        return ans % base